package com.github.hgkmail.hello.leetcode101.pointer.linkedlist;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;
import com.github.hgkmail.hello.leetcode101.base.ListNode;

//原链表：1->2->3
//普通解法：从尾部开始链起来 3->2->1
//新的解法：遍历并修改指针方向，可迭代 1<-2<-3
public class LC206ReverseLinkedList {
    //方法1 通过call stack遍历链表，模仿DFS
    public void visit(ListNode node, ListNode[] headAndCurr) {
        //空节点
        if (node==null) {
            return;
        }
        //最后一个节点
        if (node.next==null) {
            headAndCurr[0]=node; //head
            headAndCurr[1]=node; //curr
            return;
        }
        //非最后一个节点
        visit(node.next, headAndCurr);
        headAndCurr[1].next=node;
        node.next=null;
        headAndCurr[1]=node;
    }

    //从尾节点开始串起
    public ListNode reverseList(ListNode head) {
        //base case
        if (head==null || head.next==null) {
            return head;
        }
        ListNode[] headAndCurr = new ListNode[2];
        visit(head,headAndCurr);
        return headAndCurr[0];
    }

    //方法2 改变指针方向，迭代
    public ListNode reverseList2(ListNode head) {
        //不足2个节点
        if (head==null || head.next==null) {
            return head;
        }
        //改变指针方向 prev->curr
        ListNode prev=null;
        ListNode curr=head;
        ListNode temp;
        while (curr!=null) {
            temp = curr.next; //暂时保存起来
            curr.next=prev; //改变指针方向
            prev=curr;
            curr=temp;
        }
        return prev;
    }

    //方法3 改变指针方向，递归
    public ListNode reverseList3(ListNode head, ListNode prev) {
        if (head==null) {
            return prev;
        }
        ListNode temp=head.next; //暂时保存起来
        head.next=prev;
        return reverseList3(temp, head);
    }

    public static void main(String[] args) {
        ListNode a, b, c;
        c=new ListNode(3, null);
        b=new ListNode(2, c);
        a=new ListNode(1, b);
        CommonUtil.printLinkedList(a);

//        ListNode[] headAndCurr=new ListNode[2];
//        new LC206ReverseLinkedList().visit(a, headAndCurr);
//        printLinkedList(headAndCurr[0]);

//        printLinkedList(new LC206ReverseLinkedList().reverseList2(a));
        CommonUtil.printLinkedList(new LC206ReverseLinkedList().reverseList3(a, null));
    }

}
